#leetcode题目200：岛屿数量
#难度：中等
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：DFS



#题目分析：
# 1.岛屿问题， 本质上是连通区域问题，种子填充法、传染法。
from typing import List
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        岛屿数量
        给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
        岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
        此外，你可以假设该网格的四条边均被水包围。
        """
        if not grid or not grid[0]:
            return 0
        
        m = len(grid)  # 行数
        n = len(grid[0])  # 列数
        res = 0
        
        # 遍历整个网格
        for y in range(m):
            for x in range(n):
                if grid[y][x] == '1':
                    res += 1
                    self.infect(grid, x, y, m, n)
        
        return res
    
    def infect(self, grid: List[List[str]], x: int, y: int, m: int, n: int) -> None:
        """
        感染函数：使用DFS标记所有连通的陆地
        :param grid: 二维网格
        :param x: 当前列坐标
        :param y: 当前行坐标
        :param m: 网格行数
        :param n: 网格列数
        """
        # 边界检查
        if x < 0 or x >= n or y < 0 or y >= m:
            return
        
        # 如果当前格子是陆地，则进行感染
        if grid[y][x] == '1':
            grid[y][x] = '.'  # 标记为已访问
        else:
            return  # 如果是水或已访问过的陆地，直接返回
        
        # 递归感染四个方向的相邻格子
        self.infect(grid, x + 1, y, m, n)  # 右
        self.infect(grid, x - 1, y, m, n)  # 左
        self.infect(grid, x, y + 1, m, n)  # 下
        self.infect(grid, x, y - 1, m, n)  # 上


#测试数据
grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]
#预期输出：1
solution = Solution()
print(solution.numIslands(grid))


grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
#预期输出：3
solution = Solution()
print(solution.numIslands(grid))
